COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00019 ENDMK
C⊗;
\input macro[1,mps]
\magnification\magstephalf
\leftline{\sevenrm A86.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, January 31, 1989}
\leftline{\sevenrm Unpublished Draft}
\bigskip
\noindent {\bf 1.  EXAMPLES}
\medskip
\noindent {\bf 1.1  Finite automata}
\medskip
The simplest machine that we consider has only one device, a finite
memory.  This kind of machine is called a {\it finite automaton (FA)}.

One possible use for a finite memory is to store a single character.
Thus a finite automaton can test whether the first character of its input
is the same as the last character.

An FA that accepts $\{a\{0,\ldots,9\}↑\kstar b \st a = b\}$

A finite memory can also store a single number in the finite range
$0,\ldots,m-1$.  This makes it possible to count modulo $m$, so a
finite automaton can test whether the number of characters in its input
is a multiple of $m$.

An FA that accepts $\{w \st |w| \equiv 0 \pmod{5}\}$

noindent{\bf Exercise 1}  Design an FA that tests whether its 
input contains an odd number of 1's.

A (large) finite memory can store the $k$ characters most recently
read.  By doing so, a finite automaton can test whether its input
contains, as a subsequence, a fixed sequence of characters.

\noindent An FA that accepts $\{\{0,1\}↑\kstar 011 \{0,1\}↑\kstar\}$

Notice that in this example we used eight states in order to store a
sequence of three characters.  It may appear that in general $2↑k$
states are needed to in order to test for a $k$-bit pattern.  However,
we will see *** where? *** how to construct much smaller finite
automata for pattern matching.

\noindent{\bf 1.2  Unsigned-Counter Machines}
\medskip
The first infinite device that we consider is the unsigned counter.  A
machine with a finite memory and one unsigned counter is called an
{\it unsigned-counter machine} or OUCM (the ``O'' stands for {\it
one}).  We can use the counter to test whether the input is a string
of $a$'s followed by an equal number of $b$'s.

\noindent An OUCM that accepts $\{a↑nb↑n \st n \geq 0\}$
\medskip
\noindent{\bf Exercise 2}  Design OUCM's that accept the following languages:
\medskip
\item {1.}  $\{a↑nba↑n:n \geq 0\}$
\item {2.}  $\{a↑nb↑na↑mb↑m:\hbox{m}\geq 0\hbox {and n}\geq 0\}$
\medskip
By counting up twice as fast as it counts down, an OUCM can test
whether the input consists of a string of $a$'s followed by twice as
many $b$'s:

\noindent An OUCM that accepts $\{a↑nb↑{2n} \st n \geq 0\}$  
\medskip
Design an OUCM that accepts $\{a↑{2n}b↑{3n} \st n \geq 0\}
\medskip
When we write arithmetic expressions, such as $7(6 + (3 + 1)(4 + 5))$,
we use parentheses to force certain operations to be performed first.
A sequence of parentheses that could be used in a well-formed arithmetic
expression is called {\it balanced}.  In the example above, the
sequence of parentheses is $(()())$.  Formally, $\lambda$ is
balanced, and a nonempty string is balanced if it has either of the
following two forms:

\item {$\bullet$}$(w) \hbox {where} w$ is balanced, or
\item {$\bullet$} $wx \hbox {where} w$ and $x$ are both balanced.

The following exercise will make it easy for us to construct an
OUCM that tests whether its input is a string of balanced parentheses.

\noindent{\bf Exercise 4} Show that $w$ is a string of balanced 
parentheses if and only if
\medskip
\item{$\bullet$} $w$ contains equal numbers of $($'s and $)$'s, and
\item{$\bullet$} every prefix of $w$ contains at least as many $($'s as $)$'s.
\medskip
By counting the number of $($'s minus the number of $)$'s, an OUCM
can test for balanced parentheses.

An OUCM that accepts $\{w:w$ is a sequence of balanced parentheses$\}$

\noindent{2  SIGNED-COUNTER MACHINES}
\medskip
A signed-counter machine (OSCM) has a finite memory and one signed
counter.  Since the counter is allowed to contain negative values, it
is easy for an OSCM to test whether a string contains an equal number
of $a$'s and $b$'s.  (Try this with an OUCM to see why it is tricky.)

\noindent An OSCM that accepts $\{w:w$ contains an equal number
of $a$'s and $b$'s}\}$}
\medskip
\noindent{\bf Exercise 5} Design OSCM's that determine whether the input contains
\medskip
\item {1.}  more $a$'s than $b$'s
\item {2.}  twice as many $a$'s as $b$'s
\medskip
*** Where? *** we will see that every language accepted by an OSCM
is also accepted by an OUCM, and vice versa.
\medskip
\noindent {\bf 2.1  Queue Machines}
\medskip
A queue machine consists of a finite memory and one queue.  Because
symbols leave a queue in the same order as they enter, a queue machine
can easily test whether a string has the form $w\#w$.

A queue machine that accepts $\{w\#w:w \in \{0,1\}↑\star\}$}
\medskip
\noindent{\bf 2.2  Stack Machines}
\medskip
A stack machine consists of a finite memory and one stack.  Notice
that characters are popped off of a stack in the reverse of the order
they are pushed on.  Let $w↑R$ denote the reverse of the string $w$.
A stack machine can determine whether its input is of the form
$w\#w↑R$, where $w \in \Sigma↑\star$ and $\# \notin \Sigma$.  (The
$\#$ character indicates where $w$ ends and $w↑R$ begins.  To see why
this is important, try to design a stack machine that tests whether
its input is of the form $ww↑R$.)

A stack machine that accepts $\{w\#w↑R \st w \in \{0,1\}↑*\}$

\noindent{\bf Exercise 6}  Design a stack machine that accepts 
$\{a↑nb↑ma↑mb↑n:m \geq 0\hbox {and} n \geq 0$\}$.
\medskip
A sequence of parentheses ``()'' and brackets ``[]'' is {\it balanced}
if it equal to the $\lambda$ or else if it has one of the
following forms
\medskip
\item $(w)$ or $[w]$ where $w$ is balanced, or
\item $wx$ where $w$ and $x$ are both balanced.
\medskip
A stack machine can test whether its input is a balanced sequence of
parentheses and brackets.

A stack machine that accepts $\{w:w$ is a balanced sequence
of parentheses and brackets$\}$
\medskip
\noindent {\bf 2.3  2-Counter Machines}
\medskip
A 2-counter machine has two counters and a finite memory.

A 2-counter machine that accepts $\{a↑nb↑ma↑nb↑m:m \geq 0 \hbox{and $n \geq 0$}\}$.}

\subsection{Turing Machines}

\mumble{Is there anything simple enough to describe here?}

We will see \mumble{where} that every language accepted by a Turing
machine, a 2-counter machine, or a queue machine, is in fact accepted
by all three.

\section{Examples of Nondeterminism}

\mumble{need an NFA example}

\subsection{Counter Machines}

In a previous section we saw that a DOUCM can test whether its input
consists of a string of $a$'s followed by an equal number of $b$'s.
We also saw that a DOUCM can test whether its input consists of a
string of $a$'s followed by {\em twice as many} $b$'s.  Now we will
see how a NOUCM can test whether its input satisfies at least one of
those conditions.  The NOUCM succeeds where the DOUCM cannot, because
the NOUCM decides nondeterministically whether to count up by one's or
by two's.

\caption{An NOUCM that accepts
         $\{a↑mb↑n \st \mbox{$n = m$ or $n = 2m$}\}$}

\begin{exercise}
Design an NOUCM that accepts
$\{w \st \mbox{$\occurences{a}{w} = 2 \occurences{b}{w}$ or
               $2\occurences{a}{w} =  \occurences{b}{w}$}\}$.
\end{exercise}

We have seen how nondeterminism allows machines to test for the
disjunction (or) of two conditions.  In the next example we see that
sometimes it is possible to convert a negation into a disjunction.
Consider the language $L = \{a↑ib↑jc↑k \st \neg (i = j = k)\}$.  By
DeMorgan's laws, $L = \{a↑ib↑jc↑k \st \mbox{$(i \neq j)$ or $i \neq
k$}\}$.

\caption{An NOSCM that accepts $\{a↑ib↑jc↑k \st \neg (i = j = k)\}$}

\begin{exercise}
Design an NOSCM that accepts that set of all strings over $\{a,b,c\}↑\kstar$
that are not of the form $a↑nb↑nc↑n$.
Hint: Do not forget strings like $cba$.
\end{exercise}

For our next example of nondeterminism, we consider a nondeterministic
stack machine (NSM, NPDA).  Recall that a DSM can test whether its
input is of the form $w\#w↑R$ by pushing each character read until a
$\#$ is encountered, then popping each character read.  An NSM can
test whether its input is of the form $ww↑R$ by pushing each chracter
read until it {\em nondeterministically guesses} that the middle of
the string has been reached, then popping each character read.  Notice
that this is a stronger use of nondeterminism than in the previous
examples, where the machine simply guessed one of two alternatives.

\caption{An NSM that accepts $\{ww↑R \st w \in \{0,1\}↑\kstar\}$}

\begin{exercise}
The set of palindromes over $\Sigma$ is $\{w \in \Sigma \st w = w↑R\}$.
\begin{enumerate}
\item
Construct an NSM that accepts the set of all palindromes over $\{0,\ldots,7\}$.
\item
Construct such an NSM with only two stack symbols.  Hint: Each number
between 0 and 7 can be represented as a three bit binary sequence,
\eg, $3 = 011$.  Use the finite control to convert between the binary
representation and the octal representation of characters.
\end{enumerate}
\end{exercise}

\begin{exercise}
Design an NOSCM that accepts $\{wx \in \{0,1\}↑\kstar \st w \neq x\}$.
Hint: If $w$ and $x$ differ, then they differ somewhere, so $w \in
\Sigma↑ia\Sigma↑j$ and $x \in \Sigma↑ib\Sigma↑j$ for some $i$ and $j$,
where $a \neq b$.  Thus $wx \in \Sigma↑ia\Sigma↑kb\Sigma↑j$ where
$k = j + i$. Nondeterministically guess when the first $i$ characters
have been read and when the next $k$ characters have been read.  Use
the counter to make sure that $k = j + i$.
\end{exercise}
\end{document}